Hệ số cân bằng

Hệ số cân bằng của cây T là hiệu số giữa các chiều cao của cây con trái và cây con phải của nó. Ký hiệu hệ số cân bằng của cây con gôc u là balance(u). Hệ số cân bằng của cây T là balance(T).

Nếu với mọi đỉnh u của T ta có balance(u)= 0 thì T được gọi là cây cân bằng hoàn toàn; Nếu balance(T) > 0, nghĩa là cây con phải cao hơn cây con trái T được gọi là cây lệch phải;Nếu balance(T)< 0, nghĩa là cây con trái cao hơn cây con phải T được gọi là cây lệch trái.

Cân bằng AVL và cây AVL

Các cây tìm kiếm nhị phân được xây dựng theo phương pháp chèn thông thường có thể có những biến dạng mất cân đối nghiêm trọng, chẳng hạn có thể hoàn toàn lệch phải (tất cả các nút trong chỉ có con phải) hoặc lệch trái (tất cả các nút trong chỉ có con trái). Trong các trường hợp này chi phí cho việc tìm kiếm trong trường hợp xấu nhất đạt tới n (n là số nút trên cây). Nếu có một cây tìm kiếm nhị phân cân bằng hoàn toàn, chi phí đó chỉ xấp xỉ log2n. Tuy nhiên nhiều khi không thể xây dựng một cây tìm kiếm nhị phân như vậy cho mọi dãy khóa. G.M. Adelson-Velsky và E.M. Landis đã đề xuất một tiêu chuẩn cân bằng (sau này gọi là cân bằng AVL), giảm nhẹ hơn so với cân bằng hoàn toàn.Cây T được gọi là cân bằng AVL nếu tại mỗi nút u của nó hệ số cân bằng có trị số tuyệt đối không vượt quá 1. Điều đó cũng có nghĩa là với mọi nút u của T, balance(u) chỉ nhận một trong ba giá trị -1, 0, 1.Khi đó cây T cũng được gọi là cây AVL. Nếu cây con gốc tại đỉnh u là cân bằng AVL, ta cũng gọi đỉnh u là cân bằng AVL. Như vậy các lá là cân bằng AVL, cây chỉ gồm một nút gốc là cây AVL, cây chỉ gồm 2 nút là cây AVL. Cây gồm 3 nút có thể cân bằng AVL, cũng có thể không.